package com.future;

import java.util.ArrayList;
import java.util.List;

/**
 * Description: 435. 无重叠区间
 * <p>
 * 给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
 * <p>
 *  
 * <p>
 * 示例 1:
 * <p>
 * 输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
 * 输出: 1
 * 解释: 移除 [1,3] 后，剩下的区间没有重叠。
 * <p>
 * 示例 2:
 * <p>
 * 输入: intervals = [ [1,2], [1,2], [1,2] ]
 * 输出: 2
 * 解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
 * <p>
 * 示例 3:
 * <p>
 * 输入: intervals = c
 * 输出: 0
 * 解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
 *  
 * <p>
 * 提示:
 * <p>
 * 1 <= intervals.length <= 105
 * intervals[i].length == 2
 * -5 * 104 <= starti < endi <= 5 * 104
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/non-overlapping-intervals
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author weiruibai.vendor
 * Date: 2023/3/24 15:07
 */
public class Solution_435 {

    private static Solution_435 getInstance() {
        return new Solution_435();
    }

    public static void main(String[] args) {
        int[][] intervals = new int[][]{{1, 2}, {1, 2}, {1, 2}};
        intervals = new int[][]{{1, 2}, {2, 3}, {3, 4}, {1, 3}};
        System.out.println(getInstance().eraseOverlapIntervals(intervals));
    }

    public int eraseOverlapIntervals(int[][] intervals) {
        int N = intervals.length;
        if (N == 1) {
            return 0;
        }
        int ans = 0;
        List<Info> infos = new ArrayList<>();
        for (int[] nums : intervals) {
            infos.add(new Info(nums[0], nums[1]));
        }
        infos.sort((o1, o2) -> o1.start < o2.start ? -1 : o1.start == o2.start ? 0 : 1);
        int end = infos.get(0).end;
        int start = infos.get(0).start;
        infos.remove(0);
        for (Info info : infos) {
            if (start <= end && end <= info.end) {

                end = Math.min(end, info.end);
                start = info.start;
                ans++;
            } else {
                start = info.start;
                end = info.end;
            }
        }
        return ans;
    }

    class Info {

        public Integer start;
        public Integer end;

        public Info(Integer start, Integer end) {
            this.start = start;
            this.end = end;
        }

        @Override
        public String toString() {
            return "Info{" +
                    "start=" + start +
                    ", end=" + end +
                    '}';
        }
    }
}
